집합이 시간에 따라 확장, 축소, 변경 가능한 집합을 동적 집합이라고 한다. (일반적으로 객체로 구현)
이에 삽입, 삭제, 찾기 등의 연산이 포함된 동적 집합을 사전(dictionary)라고 한다.
Dynamic Set’s Operation
- 질의(Query)
- 변경 연산
Search(S, k)
집합 S의 원소 x 중 x.key=k에 대한 포인터를 리턴, 원소가 없을 경우 NIL을 리턴
Insert(S, k)
x가 가르키는 원소를 포함하도록 집합 S를 확장
Delete(S, k)
집합 S의 원소를 가르키는 포인터 x가 주어졌을 때, S에서 x를 삭제(키값이 아닌 원소 x에 대한 포인터를 사용)
Minimum(S)
가장 큰 키를 가지는 원소에 대한 포인터를 리턴
Maximum(S)
가장 작은 키를 가지는 원소에 대한 포인터를 리턴
Successor(S, x)
집합 S에서 원소 x 다음으로 큰 원소를 가리키는 포인터를 리턴(x가 최대이면 NIL 리턴)
Predecessor(S, x)
집합 S에서 원소 x 다음으로 작은 원소를 가리키는 포인터를 리턴(x가 최소이면 NIL 리턴)
일반적으로 n개의 키를 가지는 집합에 대해 Minimum을 호출한 후, n-1번 Predecessor를 호출하면 집합을 정렬할 수 있다고 간주함